package class07


/*
	一个数组中，如果两个数的 公共因子有大于1的，则认为两个
	数之间有通路，返回数组中，最大连通组件的大小 。
	leetcode: https://leetcode.cn/problems/largest-component-size-by-common-factor/
	解法一：O(N^2)
		1. 遍历所有的两点组合，才用并查集，如果属于一个组则合并
		2. 遍历完所有的点后，做一次汇总，将最大的联通区的元素个数返回

	解法二：O(N*根号K) K 为 num 的上线
		1. 遍历第一个数的时候，直接对因子拆分，1-根号num，遍历，寻找因子，放入一个映射表
		2. 后续循环，拆分每个数，到表中寻找是否有联通域，有的话直接联通，没有的话注册表
*/

// 解法一：事件超过限制
import (
	"math"
	"traning/algorithm/utility/unionset"
)

func largestComponentSize1(nums []int) int {
	nNums := make([]interface{}, len(nums))
	for i:=0; i<len(nNums); i++ {
		nNums[i] = nums[i]
	}
	myu := unionset.NewUnionSet(nNums)
	for i:=0; i<len(nums); i++ {
		for j:=i+1; j<len(nums); j++ {
			if gcd(nums[i], nums[j]) != 1 {
				myu.Union(nums[i], nums[j])
			}
		}
	}
	return myu.MaxUnionSize()
}


// 辗转相除法，又称 欧几里得算法 获取最大公约数
func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}


// 方式二，可以通过
func largestComponentSize2(nums []int) int {
	// 共约数表
	mdMap := make(map[int]int)
	nNums := make([]interface{}, len(nums))
	for i:=0; i<len(nNums); i++ {
		nNums[i] = nums[i]
	}
	myu := unionset.NewUnionSet(nNums)
	for i:=0; i<len(nNums); i++ {
		if _, ok := mdMap[nums[i]]; ok {
			myu.Union(nNums[i], nNums[mdMap[nums[i]]])
		} else {
			mdMap[nums[i]] = i
		}
		for j:=2; j<=int(math.Sqrt(float64(nNums[i].(int)))); j++ {
			if nNums[i].(int) % j == 0 {
				otherCD := nNums[i].(int)/j
				if _, ok := mdMap[j]; ok {
					myu.Union(nNums[i], nNums[mdMap[j]])
				} else {
					mdMap[j] = i
				}
				if _, ok := mdMap[otherCD]; ok {
					myu.Union(nNums[i], nNums[mdMap[otherCD]])
				} else {
					mdMap[otherCD] = i
				}
			}
		}
	}
	return myu.MaxUnionSize()
}


// 3. 逻辑合并
func largestComponentSize3(nums []int) int {
	// 共约数表
	mdMap := make(map[int]int)
	nNums := make([]interface{}, len(nums))
	for i:=0; i<len(nNums); i++ {
		nNums[i] = nums[i]
	}
	myu := unionset.NewUnionSet(nNums)
	for i:=0; i<len(nNums); i++ {
		for j:=1; j<=int(math.Sqrt(float64(nNums[i].(int)))); j++ {
			if nNums[i].(int) % j == 0 {
				if j != 1 {
					if _, ok := mdMap[j]; ok {
						myu.Union(nNums[i], nNums[mdMap[j]])
					} else {
						mdMap[j] = i
					}
				}
				otherCD := nNums[i].(int)/j
				if otherCD != 1 {
					if _, ok := mdMap[otherCD]; ok {
						myu.Union(nNums[i], nNums[mdMap[otherCD]])
					} else {
						mdMap[otherCD] = i
					}
				}
			}
		}
	}
	return myu.MaxUnionSize()
}